অ্যাডভান্সড সর্টিং অ্যালগরিদমগুলি বড় ডেটাসেটকে দ্রুত এবং কার্যকরভাবে সাজাতে ব্যবহৃত হয়। এখানে তিনটি জনপ্রিয় অ্যাডভান্সড সর্টিং অ্যালগরিদম: Merge Sort, Quick Sort, এবং Heap Sort নিয়ে আলোচনা করা হলো।
১. Merge Sort
বিবরণ: Merge Sort একটি বিভাজন এবং বিজয় (Divide and Conquer) ভিত্তিক অ্যালগরিদম। এটি তালিকাকে দুটি ছোট তালিকায় বিভক্ত করে এবং পরে সেগুলোকে মার্জ করে সাজায়।
সময় জটিলতা:
- Worst Case: O(n log n)
- Best Case: O(n log n)
- Average Case: O(n log n)
কাজের পদ্ধতি:
- তালিকাকে মাঝখানে বিভক্ত করুন যতক্ষণ না প্রত্যেক তালিকা একটি একক উপাদান থাকে।
- ছোট ছোট তালিকাগুলোকে মার্জ করুন, সাজিয়ে রাখুন।
উদাহরণ:
def merge_sort(arr):
if len(arr) > 1:
mid = len(arr) // 2 # তালিকা ভাগ করা
left_half = arr[:mid]
right_half = arr[mid:]
merge_sort(left_half) # বাম অংশের জন্য মার্জ সোর্ড
merge_sort(right_half) # ডান অংশের জন্য মার্জ সোর্ড
i = j = k = 0
# মার্জ করা
while i < len(left_half) and j < len(right_half):
if left_half[i] < right_half[j]:
arr[k] = left_half[i]
i += 1
else:
arr[k] = right_half[j]
j += 1
k += 1
# বাকি উপাদানগুলো কপি করা
while i < len(left_half):
arr[k] = left_half[i]
i += 1
k += 1
while j < len(right_half):
arr[k] = right_half[j]
j += 1
k += 1
# ব্যবহার
arr = [38, 27, 43, 3, 9, 82, 10]
merge_sort(arr)
print(arr) # আউটপুট: [3, 9, 10, 27, 38, 43, 82]
২. Quick Sort
বিবরণ: Quick Sort একটি খুব কার্যকরী বিভাজন এবং বিজয় ভিত্তিক অ্যালগরিদম। এটি একটি পিভট (pivot) নির্বাচন করে, এবং পিভটের তুলনায় ছোট এবং বড় উপাদানগুলোকে পৃথক করে।
সময় জটিলতা:
- Worst Case: O(n²) (যখন তালিকাটি ইতিমধ্যে সাজানো থাকে)
- Best Case: O(n log n)
- Average Case: O(n log n)
কাজের পদ্ধতি:
- একটি পিভট নির্বাচন করুন (সাধারণত প্রথম, শেষ, বা মাঝের উপাদান)।
- উপাদানগুলোকে পিভটের সাথে তুলনা করুন এবং পিভটের বাম এবং ডানদিকে উপাদানগুলো সাজান।
- পুনরায় অ্যালগরিদমটি বাম ও ডান উপ-তালিকায় প্রয়োগ করুন।
উদাহরণ:
def quick_sort(arr):
if len(arr) <= 1:
return arr
pivot = arr[len(arr) // 2] # পিভট নির্বাচন
left = [x for x in arr if x < pivot]
middle = [x for x in arr if x == pivot]
right = [x for x in arr if x > pivot]
return quick_sort(left) + middle + quick_sort(right)
# ব্যবহার
arr = [38, 27, 43, 3, 9, 82, 10]
sorted_arr = quick_sort(arr)
print(sorted_arr) # আউটপুট: [3, 9, 10, 27, 38, 43, 82]
৩. Heap Sort
বিবরণ: Heap Sort একটি তুলনামূলক অ্যালগরিদম যা ডেটাকে সাজাতে একটি হিপ ডেটা স্ট্রাকচার ব্যবহার করে। এটি প্রথমে একটি ম্যাক্স হিপ (Max Heap) তৈরি করে এবং পরে সর্বাধিক উপাদানটিকে বের করে হিপটি পুনরায় সাজায়।
সময় জটিলতা:
- Worst Case: O(n log n)
- Best Case: O(n log n)
- Average Case: O(n log n)
কাজের পদ্ধতি:
- একটি ম্যাক্স হিপ তৈরি করুন।
- সর্বাধিক উপাদান (root) বের করুন এবং হিপের শেষ উপাদানকে root-এ স্থানান্তর করুন।
- হিপটি পুনরায় সাজান।
- এই প্রক্রিয়া পুনরাবৃত্তি করুন যতক্ষণ না হিপ খালি হয়ে যায়।
উদাহরণ:
def heapify(arr, n, i):
largest = i
left = 2 * i + 1
right = 2 * i + 2
if left < n and arr[i] < arr[left]:
largest = left
if right < n and arr[largest] < arr[right]:
largest = right
if largest != i:
arr[i], arr[largest] = arr[largest], arr[i] # বিনিময়
heapify(arr, n, largest)
def heap_sort(arr):
n = len(arr)
for i in range(n // 2 - 1, -1, -1):
heapify(arr, n, i)
for i in range(n - 1, 0, -1):
arr[i], arr[0] = arr[0], arr[i] # সর্বাধিক উপাদান বের করা
heapify(arr, i, 0)
# ব্যবহার
arr = [38, 27, 43, 3, 9, 82, 10]
heap_sort(arr)
print(arr) # আউটপুট: [3, 9, 10, 27, 38, 43, 82]
উপসংহার
Merge Sort: একটি স্থির সময় জটিলতা O(n log n) সহ একটি বিভাজন এবং বিজয় ভিত্তিক অ্যালগরিদম। এটি খুব কার্যকরী কিন্তু অতিরিক্ত স্থান ব্যবহার করে।
Quick Sort: গড় ক্ষেত্রে O(n log n) সময় জটিলতার সাথে দ্রুত এবং কার্যকরী, তবে খারাপ ক্ষেত্রে O(n²) হতে পারে।
Heap Sort: O(n log n) সময় জটিলতার সাথে একটি তুলনামূলক অ্যালগরিদম যা স্থির স্থান ব্যবহারের সুবিধা প্রদান করে।
প্রতিটি অ্যালগরিদমের নিজস্ব সুবিধা এবং অসুবিধা রয়েছে, এবং তাদের ব্যবহার করা উচিত সমস্যা ও ডেটার প্রকারভেদ অনুযায়ী।
Read more
